//
// Description: 797. 所有可能的路径
// Created by Loading on 2021/8/25.
//

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {
    int n = graph.size();
    vector<vector<int>> res;
    // 一条路径
    vector<int> path;

    function<void(int)> dfs = [&](int pos) {
        // 遍历至终点
        if (pos == n - 1) {
            res.emplace_back(path);
            return;
        }
        for (auto &x : graph[pos]) {
            path.emplace_back(x);
            dfs(x);
            // 回溯
            path.pop_back();
        }
    };

    path.emplace_back(0);
    dfs(0);
    return res;
}

int main() {
    vector<vector<int>> graph = {{1, 2},
                                 {3},
                                 {3},
                                 {}};
    vector<vector<int>> res = allPathsSourceTarget(graph);
    for (auto &v : res) {
        for (auto &x : v) {
            cout << x << " ";
        }
        cout << endl;
    }

    return 0;
}